//
// Created by ASUS on 2024/7/9/星期二.
//
#include <bits/stdc++.h>
using namespace std;

class StringHash {
private:
	vector<int> pow_base,pre_hash;
	int BASE=13331;
	const int MOD = 1'070'777'777;
public:
	//哈希主串
	StringHash(string&target) {
//		mt19937 gen{random_device{}()};
		mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
		BASE = uniform_int_distribution<>(8e8, 9e8)(rng); // 随机 base，防止 hack
		int n = target.size();
		pow_base.resize(n + 1); // pow_base[i] = base^i
		pre_hash.resize(n + 1); // 前缀哈希值 pre_hash[i] = hash(s[:i])
		pow_base[0] = 1;
		for (int i = 0; i < n; i++) {
			pow_base[i + 1] = (long long) pow_base[i] * BASE % MOD;
			pre_hash[i + 1] = ((long long) pre_hash[i] * BASE + target[i]) % MOD; // 秦九韶算法计算多项式哈希
		}
	}
	// 计算 target[l] 到 target[r-1] 的哈希值
	long long getHash(int l, int r) {
		return ((pre_hash[r] - (long long) pre_hash[l] * pow_base[r - l]) % MOD + MOD) % MOD;
	}
	//哈希要匹配的子串
	long long getHash(string& t) {
		long long res = 0;
		for (char& ch : t) {
			res = (res * BASE + ch) % MOD;
		}
		return res;
	}
};